package com.platform.modules.alg.alglib.p67;

public class P67 {

    private final int maxn = 10000;
    int n;
    int a[][] = new int[maxn][maxn];
    int c[][] = new int[maxn][maxn];

    // 区间长度
    int lowbit(int i) {
        return (-i) & i;
    }

    // a[x][y] 加上z
    void add(int x, int y, int z) {
        for (int i = x; i <= n; i += lowbit(i))
            for (int j = y; j <= n; j += lowbit(j))
                c[i][j] += z;
    }

    // 求左上角(1,1)到右下角(x,y)矩阵区间和
    int sum(int x, int y) {
        int s = 0;
        for (int i = x; i > 0; i -= lowbit(i))
            for (int j = y; j > 0; j -= lowbit(j))
                s += c[i][j];
        return s;
    }

    // 求左上角(x1,y1)到右下角(x2,y2)子矩阵区间和
    int sum(int x1, int y1, int x2, int y2) {
        return sum(x2, y2) - sum(x1 - 1, y2) - sum(x2, y1 - 1) + sum(x1 - 1, y1 - 1);
    }

    public String output = "";

    public String cal(String input) {
        String[] line = input.split("\n");
        n = Integer.parseInt(line[0]);

        for (int i = 1; i <= n; i++) {
            String[] nums = line[i].split(" ");
            for (int j = 1; j <= n; j++) {
                a[i][j] = Integer.parseInt(nums[j - 1]);
                add(i, j, a[i][j]); // 加入树状数组
            }
        }

        int x1, y1, x2, y2;
        String[] query = line[n + 1].split(" ");
        x1 = Integer.parseInt(query[0]);
        y1 = Integer.parseInt(query[1]);
        x2 = Integer.parseInt(query[2]);
        y2 = Integer.parseInt(query[3]);
        output += sum(x1, y1) + "\n";
        output += sum(x1, y1, x2, y2) + "";

        return output;
    }
}
